/**
 *    Copyright (C) 2008, 2009 Victor Smirnov <aist11@gmail.com>
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 *    See LICENSE.exceptions in the root folder of this project for possible
 *    exceptions
 *
 */

#ifndef _CUBEFS_CORE_BTREE_MODEL_FIND_HPP
#define	_CUBEFS_CORE_BTREE_MODEL_FIND_HPP

#include <cubefs/api/models/logs.hpp>
#include <cubefs/core/container/container.hpp>
#include <cubefs/core/btree/pages/tools.hpp>
#include <cubefs/core/btree/names.hpp>

#define CUBEFS_SOURCE "cubefs/core/btree/model/find.hpp:" CUBEFS_AT

namespace cubefs    {
namespace ctr       {

using namespace cubefs::btree;

CUBEFS_MODEL_PART_BEGIN(cubefs::btree::FindName)

    typedef typename Base::Types                                                Types;
    typedef typename Base::PageMgr                                              PageMgr;

    typedef typename PageMgr::Page                                              Page;
    typedef typename Page::ID                                                   ID;
    typedef typename PageMgr::Transaction                                       Transaction;

    typedef typename Types::NodeBase                                            NodeBase;
    typedef typename Types::Counters                                            Counters;
    typedef typename Base::Iterator                                             Iterator;

    typedef typename Types::Pages::NodeDispatcher                               NodeDispatcher;
    typedef typename Types::Pages::RootDispatcher                               RootDispatcher;
    typedef typename Types::Pages::LeafDispatcher                               LeafDispatcher;
    typedef typename Types::Pages::NonLeafDispatcher                            NonLeafDispatcher;

    typedef typename Types::Pages::Node2RootMap                                 Node2RootMap;
    typedef typename Types::Pages::Root2NodeMap                                 Root2NodeMap;

    typedef typename Types::Pages::NodeFactory                                  NodeFactory;

    typedef typename Base::Key                                                  Key;
    typedef typename Base::Value                                                Value;

    static const Int Indexes                                                    = Types::Indexes;

    template <
            typename Comparator
    >
    struct FindFn {
        Iterator        i_;
        bool            rtn_;
        NodeBase*       node_;

        Int             idx_;
        Key             key_;
        
        Int             c_;

        Comparator&     cmp_;
        
        MyType&         model_;

    public:
        FindFn(Comparator& cmp, Key key, Int c, MyType &model):
            i_(model), rtn_(false), node_(NULL),
            key_(key), c_(c), model_(model),
            cmp_(cmp) {}

        template <typename Node>
        void operator()(Node *node)
        {
            rtn_ = false;
            idx_ = cmp_.Find(node, c_, key_);

            if (idx_ >= 0)
            {
                if (!node->is_leaf()) {
                    node_ = model_.GetChild(node, idx_);
                }
                else {
                    node_           = node;
                    i_.page()       = node;
                    i_.key_idx()    = idx_;
                    cmp_.SetupIterator(i_);

                    i_.SetEof(false);
                    i_.SetEmpty(false);

                    i_.Init();
                    rtn_            = true;
                }
            }
            else if (cmp_.for_insert_ && cmp_.CompareMax(key_, node->map().max_key(c_)))
            {
                if (!node->is_leaf())
                {
                    idx_     = node->map().size() - 1;
                    node_   = model_.GetChild(node, idx_);
                }
                else
                {
                    node_           = node;
                    i_.page()       = node;
                    i_.key_idx()    = node->map().size();
                    cmp_.SetupIterator(i_);

                    i_.SetEmpty(false);
                    i_.SetEof(true);

                    i_.Init();
                    rtn_            = true;
                }
            }
            else {
                CUBEFS_TRACE(model_, "EMPTY Iterator");
                node_           = NULL;
                i_.page()       = NULL;
                i_.key_idx()    = -1;
                i_.state()      = 0;
                cmp_.SetupIterator(i_);
                
                i_.SetEof(true);
                i_.SetEmpty(true);

                i_.Init();
                rtn_ = true;
            }
        }

        const Iterator iterator() const {
            return i_;
        }

        bool rtn() const {
            return rtn_;
        }

        NodeBase* node() {
            return node_;
        }

    };

    template <typename Comparator>
    const Iterator _find(Key key, Int c, bool for_insert)
    {
        CUBEFS_TRACE(me_, "_find", key, c, for_insert);

        NodeBase *node = me_.GetRoot();
        if (node != NULL)
        {
            Comparator cmp(for_insert);
            while(1)
            {
                FindFn<Comparator> fn(cmp, key, c, me_);
                NodeDispatcher::Dispatch(node, fn);

                if (fn.rtn_)
                {
                    return fn.i_;
                }
                else {
                    node = fn.node();
                    cmp.AdjustKey(key);
                }
            }
        }
        else {
            CUBEFS_TRACE(me_, "_find: No Root for Model");
            return Iterator(me_);
        }
    }

    const Iterator FindLE(Key key, Int i, bool for_insert) {
        CUBEFS_MODEL_METHOD_IS_NOT_IMPLEMENTED();
    }

    const Iterator FindLT(Key key, Int i, bool for_insert) {
        CUBEFS_MODEL_METHOD_IS_NOT_IMPLEMENTED();
    }

CUBEFS_MODEL_PART_END

}
}

#undef CUBEFS_SOURCE

#endif	//_CUBEFS_CORE_MODELS_KVMAP_MODEL_FIND_HPP
